This invention relates in general to the asynchronous transmission of digital signals, and more particularly relates to a First-In-First-Out (FIFO) buffer in which a historical trend of the direction (ascending or descending) of change of the difference between counted READ clock pulses and counted WRITE clock pulses is developed to generate buffer capacity information.
First-In-First-Out (FIFO) buffer memories are dual port memories having characteristics which are highly useful in many applications. In particular, such memories allow the writing of data to the memory and the reading of data from the memory simultaneously, and at independent rates limited only by the speed capability of the memory itself and devices to which the FIFO is connected.
By way of example, a typical system utilizing FIFO buffers is a computer system in which a CPU is connected to a keyboard, a monitor, a printer, a memory storage device, a modem, and a network. In transmitting data from one piece of equipment to another, such transmission often requires communication between extremely fast operating equipment such as the CPU, and other slower operating equipment such as storage devices and printers.
The most efficient use of such a system is realized when the various interconnected components of the system can communicate asynchronously, so that the fast operating equipment is not slowed down by the slower operation of the peripheral equipment. Thus, FIFO memories are utilized between the components for storing data written thereto by a first piece of equipment at one speed and read therefrom by destination equipment at another speed.
Since asynchronous FIFO""s are simultaneously performing both READ and WRITE operations, the available space in the FIFO is constantly changing. When the speed of the WRITE operation, which adds data to the FIFO, exceeds the speed of the READ operation, which retrieves data from the FIFO, the available space in the FIFO gradually decreases in proportion to the difference in speed of the WRITE and READ clock signals which clock the data in and out of the FIFO. Conversely, when the speed of the READ operation exceeds that of the WRITE operation, the available space in the FIFO gradually increases, again in proportion to the difference in speed of the READ and WRITE clock signals.
For such a system to function properly, it is necessary that real-time knowledge of the capacity status of the FIFO be available at all times. For example, when the buffer is full, the equipment transmitting data to the buffer should be signaled so that further transmission cannot be accomplished until memory storage space again becomes available. Likewise, the destination equipment should be signaled by the buffer when the memory storage is empty so that further reading of the buffer is not attempted until additional data has been written to the buffer by the transmitting equipment. If an attempt is made to write data to a full FIFO, the data is usually ignored; if an attempt is made to read data from an empty FIFO, the last block of valid data is usually reread. Each of these results is undesirable and can cause delay and/or data errors.
To accomplish the above-described signaling function, asynchronous FIFO buffers are typically equipped with status flag circuitry to detect and signal various degrees of fullness of the buffer array, e.g., to generate EMPTY flags, FULL flags, HALF-FULL flags, and flags indicating other various fractions of the total memory capacity (partial-capacity flags). The partial-capacity flags may serve to signal to a device that the READ or WRITE operation speed should be increased or decreased, if possible.
Many of these systems use binary counters connected to READ and WRITE clocks which are also connected to binary adders and subtractors. The binary adders or subtractors detect the differences between the READ and WRITE pointer levels as the clock pulses from the READ and WRITE clocks are counted. These counters generate the status flags in a known manner to facilitate the smooth operation of the reading and writing process.
Because of the use of the binary adders and subtractors, and therefore the use of binary code, glitches can occur as the binary code switches from one value to another. For example, in order to switch from a binary 7 (0111) to a binary 8 (1000), all four of the digits in the binary number must change state. As the number of state-changes increases, so does the likelihood for the occurrence of glitches, since the actual switching cannot occur simultaneously. These glitches may lead to the generation of a false flag. Since the READ and WRITE clocking occurs asynchronously, no reliable glitch filtering exists in the prior art.
In an effort to reduce the potential for glitching, methods have been developed for determining the empty/full status of a FIFO memory which utilize xe2x80x9cgray coding.xe2x80x9d Gray-code refers to a system of binary numbers in which only one of the bits is different between any two consecutive numbers. Basically, the binary numbers are placed in sequence based on an order which assures that, from one digit to the next, only one bit changes state, disregarding their decimal order. Thus, in a gray-code counter, only one bit changes state due to any increment or decrement of a counter. This ensures that any errors or glitches occurring in calculation of the EMPTY or FULL flags will be less than or equal to one. Examples of such gray-code FIFO memories can be found in U.S. Pat. Nos. 5,084,841 and 5,426,756, both of which are incorporated herein fully by reference.
While known gray-code pointer counters reduce the glitching associated with changes in the counter state, they still require additions and/or subtractions to be performed in order to calculate the xe2x80x9cpartially fullxe2x80x9d or xe2x80x9cpartially emptyxe2x80x9d states. For example, in U.S. Pat. No. 5,084,841, multiple gray-code counters are utilized for each partially-full state so that, based on a Full-state value F, a lesser value Fxe2x88x92N can be determined, where N is a number selected by the user to represent an amount below FULL at which a partially-full flag will be set. In this scenario, a first gray-code counter is required to calculate the FULL state and a second gray-code counter is required to indicate the FULL-N state. This requires additional hardware, increasing the expense of the circuit and the size of the circuit. Further, none of the prior art gray-code FIFOs compensate for gray-coding errors which may occur at and around the partial capacity flags.
Thus, there is a need for a FIFO that can generate an xe2x80x9cALMOST FULLxe2x80x9d and/or xe2x80x9cALMOST EMPTYxe2x80x9d flag, compensate for gray-code switching errors, and reduce the hardware needed for implementation.
The present invention addresses the needs of the prior art by providing a FIFO which includes gray-encoded READ and WRITE counters in which ALMOST FULL and/or ALMOST EMPTY (referred to collectively as xe2x80x9cWATERMARK levelxe2x80x9d herein) flags are generated when the difference between the count values in the two counters exceeds a first threshold level and which resets the flag when the difference between the count values drops below a second, lower threshold level. In accordance with the present invention, a single gray-coded WRITE pointer counter comprises a WRITE pointer register and a gray-code increment block. A READ pointer register comprises a shift register and a gray code increment block having plural stages and storing consecutive incremental WATERMARK values, based on the READ pulse count, therein. With each successive READ clock pulse, consecutive WATERMARK values are stored in the plural-stage READ pointer register, and with each READ clock pulse these values are incremented by one. The plural WATERMARK values are compared with the current value of the WRITE pointer register. By analyzing the current WRITE pointer value in connection with the plural consecutive WATERMARK values, the direction (ascending or descending) of the compared values can be determined and, due to the redundancy available from the multi-level WATERMARK values stored in the READ pointer register, hystersis is introduced so that the ALMOST FULL or ALMOST EMPTY flags are generated only when the difference between the READ and WRITE pulses crosses the WATERMARK level.